package leetcode.code0878;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	final int mod = (int) 1e9 + 7;

	public int nthMagicalNumber(int n, int a, int b) {
		long ans = 0;
		long l = 0, r = (long) Math.min(a, b) * n;
		long lcm = this.lcm(a, b);
		while (l <= r) {
			long m = l + ((r - l) >> 1);
			long N = m / a + m / b - m / lcm;
			if (N >= n) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return (int) (ans % mod);
	}

	private long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	private long lcm(long a, long b) {
		return a * b / gcd(a, b);
	}

	@Override
	public void debug1() {
		HelpDebug.compare(2, this.nthMagicalNumber(1, 2, 3));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
		HelpDebug.compare(132710250, this.nthMagicalNumber(100000000, 30000, 21546));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug2();
		so.debug1();
		so.debug3();
		so.debug4();

	}

}
